#include<iostream>
#include<assert.h>
using namespace std;
template<class K,class V> 
struct AVLTreeNode
{
    typedef pair<const K,V> val_type;
    AVLTreeNode<K,V>* _left;
    val_type _val;
    AVLTreeNode<K,V>* _right;
    AVLTreeNode<K,V>* _parent;
    int _bf;
public:
//构造函数
//防止是对应的右值对额时候
    AVLTreeNode(const val_type& ret)
    : _left(nullptr),
    _val(ret),
    _right(nullptr),
    _bf(0),
    _parent(nullptr)
    {}

    /* data */
};
template<class K,class V>
class AVLTree
{
    typedef AVLTreeNode<K,V> Node;
    typedef pair<const K,V> val_type;
    Node * _root;
public:
    AVLTree():
    _root(nullptr)
    {}
    ~AVLTree()
    {}
    //只需要出问题节点就行
    void rotoL(Node * parent)
    {
        //进行旋转
        //保存节点
        Node * ret = parent;
        //保存上层，便于旋转完和上层建立联系
        Node * ppNode = ret->_parent;
        //因为是左单旋所以是右边高度变化
        Node * cur = ret->_right;
        //进行旋转。
        if(cur->_left)
        cur->_left->_parent = ret;
        ret->_right = cur->_left;
        cur->_left = ret;
        cur->_parent = ppNode;
        ret->_parent = cur;
        if(ppNode)
        {
            if(parent == ppNode->_left)
            {
                ppNode->_left = cur;
            }
            else
            {
                ppNode->_right = cur;
            }
        }
        else{
            _root = cur;
        }
        
        //更新对应的平衡因子
        cur->_bf = 0;
        ret->_bf = 0;
        
    }
    void rotoR(Node * parent)
    {
        Node * ret = parent;
        Node * ppNode = ret->_parent;
        Node * cur = ret->_left;
        //进行旋转
        if(cur->_right)
        cur->_right->_parent = ret;
        ret->_left = cur->_right;
        ret->_parent = cur;
        cur->_parent = ppNode;
        cur->_right = ret;
        //下层向上的链接接好还要有向下的
        if(ppNode)
        {
            if(parent == ppNode->_left)
            {
                ppNode->_left = cur;
            }
            else
            {
                ppNode->_right = cur;
            }
        }
        else{
            _root = cur;
        }
        
        cur->_bf = 0;
        ret->_bf = 0;


    }
    void rotoRL(Node * parent)
    {
        //先进行右旋，然后进行左旋
        Node * cur = parent->_right;
        Node * curl = cur->_left;
        rotoR(cur);
        rotoL(parent);
        if(!curl->_bf)
        {
            parent->_bf = cur->_bf = 0;
        }
        else if(curl->_bf == -1)
        {
            parent->_bf = 1;
            cur->_bf = curl->_bf = 0;
        }
        else if(curl->_bf== 1)
        {
            parent->_bf = curl->_bf = 0;
            cur->_bf = -1;
        }
        else{
            assert(false);
        }

    }
    void rotoLR(Node * parent)
    {
        Node * cur = parent->_left;
        Node * curr = cur->_right;
        rotoL(cur);
        rotoR(parent);
        //进行平衡因子的检查
        if(!curr->_bf)
        {
            parent->_bf = cur->_bf = 0;
        }
        else if(curr->_bf == -1)
        {
            parent->_bf = 1;
            cur->_bf = curr->_bf = 0;
        }
        else if(curr->_bf == 1)
        {
            parent->_bf = curr->_bf = 0;
            cur->_bf = -1;
        }
        else{
            assert(false);
        }

    }
    bool insert(const val_type& tem)
    {
        if(!_root)
        {
            Node * ret = new Node(tem);
            _root = ret;
            return true;
        }
        Node * cur = _root;
        //在插入的时候需要对父节点进行插入，所以还需要一个parent变量进行存储
        Node * parent = _root;
        while(cur)
        {
            parent = cur;
            if(tem.first > cur->_val.first )
            {
                //如果是大于就要向右走
                
                cur = cur->_right;
            }
            else if(tem.first < cur->_val.first) {
                cur = cur->_left;
            }
            else
            {
                return false;
            }
        }
        //但是还要检查对应的平衡因子来看看是否进行旋转，平衡
        if(parent->_val.first > tem.first)
        {
            //那就要插入左侧
            Node * ret = new Node(tem);
            parent->_bf--;
            parent->_left = ret;
            ret->_parent = parent;
            Node* tem_par = parent->_parent;
            while(tem_par)
            {
                tem_par->_bf --;
            }
        }
        else{
            //插入右侧
            Node * ret = new Node(tem);
            parent->_bf++;
            parent->_right = ret;
            ret->_parent = parent;
            Node* tem_par = parent->_parent;
            while(tem_par)
            {
                tem_par->_bf ++;
            }

        }
        //插入之后
        //检查平衡因子进行旋转
        /*平衡因子对应的树的情况
        如果节点的父节点的平衡因子是0的话那么证明，父节点左右子树等高
        如果是1或者是-1的话就证明父节点需要进行检查，对应的旋转，那么什么时候需要对其进行单旋转
        什么时候需要进行双旋转
        */
       //向上寻找异常的地方
       //也是对平衡因子进行平衡
       //不能直接用cur因为我们需要子节点的地址以便于进行旋转其实动的，就只有
       
       while(parent)
       {
        //第一个停止条件就是当父亲节点已经是0
        //还要有继续的条件就是当是+1 / -1
            if(!parent->_bf)
            {
                //不需要进行调整就可以直接进行对应
                break;
            }
            else if(abs(parent->_bf) == 1)
            {
                cur = parent;
                parent = parent->_parent;
            }
            //其中到达根节点的逻辑已经用while进行判断了
            //然后就是异常的判断
            else if(parent->_bf == 2 || parent->_bf == -2)
            {
                //进行旋转
                //根据平衡因子进行平衡
                /*
                观察两颗树可以发现，当是内侧进行插入的时候，发生平衡因子异常节点处的平衡因子
                和来源处最近的平衡因子是相反的，如果是外侧进行插入的话则就是 
                */
               if(parent->_bf + cur->_bf == 3)
               {
                //进行左单旋
                    rotoL(parent);
               }
               else if(parent->_bf + cur->_bf == -3)
               {
                    rotoR(parent);
               }
               else if(parent->_bf + cur->_bf == 1)
               {
                    rotoRL(parent);
               }
               else if(parent->_bf + cur->_bf == -1)
               {
                    rotoLR(parent);
               }
               
            }
            else{
                cout << " 不符合搜索特性" << endl;
                return false;
            }
       }
       return true;
    }
};
int main()
{
    AVLTree<int,int> tr;
    int a[] = {10,9,8,7,6,5,4,3,2,1};
    for(auto i : a)
    {
        tr.insert(make_pair(i,i));
    }
    return 0;
}
